
package com.offer.leetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * Solution03
 */
public class Solution03 {

    /**
     * 
     * @param array
     * @return
     */
    public int findRepeatNumber(final int[] array) {

        for (int i = 0; i < array.length; i++) {

            while (i != array[i]) {

                if (array[i] == array[array[i]]) {
                    return array[i];
                }

                swap(array, i, array[i]);

            }

        }

        throw new IllegalArgumentException();
    }

    private List<Integer> findRepeatNumberWithList(final int[] array) {
        final List<Integer> list = new LinkedList<>();

        // 先交换，再放
        for (int i = 0; i < array.length; i++) {

            while (array[array[i] - 1] != array[i]) {
                swap(array, i, array[i] - 1);
            }

        }

        for (int i = 0; i < array.length; i++) {

            if (array[i] -1 != i) {
                list.add(array[i]);
            }

        }

        return list;

    }

    private void swap(final int[] array, final int a, final int b) {

        final int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;

    }

    public static void main(final String[] args) {
        final Solution03 s = new Solution03();
        final int[] array = { 2, 3, 1, 2, 5, 3 };
        System.out.println(s.findRepeatNumber(array));

        List<Integer> list = s.findRepeatNumberWithList(array);

        list.forEach(System.out::println);
    }
}